// https://www.cnblogs.com/Anker/archive/2013/01/30/2882773.html
#ifndef H_CORE_RBTREE_H
#define H_CORE_RBTREE_H

#include <stdio.h>
#include <assert.h>

namespace QinChat{
    namespace Core{
        enum RBTreeColor{RED, BLACK, UNKNOW};

        template<typename T>
        struct RBTreeNode{
            T data;
            RBTreeNode* pParent;
            RBTreeNode* pLeft;
            RBTreeNode* pRight;
            RBTreeColor color;
			RBTreeNode():data(T()), pParent(nullptr), pLeft(nullptr), pRight(nullptr), color(BLACK){ }

            RBTreeNode& operator= (const RBTreeNode& o){
                data = o.data;
                pParent = o.pParent;
                pLeft = o.pLeft;
                pRight = o.pRight;
                color = o.color;
            }
        };

        template <typename T>
        class RBTree{
            public:
                explicit RBTree(void);
                ~RBTree(void);

            public:
                bool IsContains(const T& k) const;
                bool GetMinmum(T& minElem) const;
                bool GetMaxmum(T& minElem) const;
                bool GetSuccessor(const T& k,T& ret) const;
                bool GetPredecessor(const T& k,T& ret) const;
                bool Insert(const T& k);
                bool Delete(const T& k);
                void InorderWalk()const;
                RBTreeNode<T>* GetRoot() const;
                RBTreeNode<T>* SearchNode(const T& k)const;

            protected:
                RBTreeNode<T>* GetParent(RBTreeNode<T>* pNode) const;
                RBTreeNode<T>* GetLeft(RBTreeNode<T>* pNode) const;
                RBTreeNode<T>* GetRight(RBTreeNode<T>* pNode) const;
                T GetKey(RBTreeNode<T>* pNode) const;
                RBTreeColor GetColor(RBTreeNode<T>* pNode) const;
                void SetColor(RBTreeNode<T>* pNode, RBTreeColor color);
                void LeftRotate(RBTreeNode<T> *pNode);
                void RightRotate(RBTreeNode<T> *pNode);
                void InsertFixup(RBTreeNode<T> *pNode);
                void DeleteFixup(RBTreeNode<T> *pNode);
                RBTreeNode<T>* GetMaxmum(RBTreeNode<T> *pNode) const;
                RBTreeNode<T>* GetMinmum(RBTreeNode<T> *pNode) const;
                RBTreeNode<T>* GetSuccessor(RBTreeNode<T> *pNode) const;
                RBTreeNode<T>* GetPredecessor(RBTreeNode<T> *pNode) const;
               // RBTreeNode<T>* SearchNode(const T& k)const;
                void Clearn(RBTreeNode<T>* pNode);

            private:
                RBTreeNode<T>* m_pRoot = nullptr;
				static RBTreeNode<T>* NIL ;
        };
    } // Core
} // QinChat

#include "rbtree.inl"

#endif // ! H_CORE_RBTREE_H